1. Field of the Invention
The present invention generally relates to halftoning techniques in printers and, more particularly, to a system and method to print grey scale or color images using fewer colors of ink than in the original image.
2. Background Description
Most printers today can print in only a limited number of colors. Halftoning is a technique for printing a picture (or more generally displaying it on some two-dimensional medium) with small dots of a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey levels when viewed from some distance.
Error diffusion, as first described in "An Adaptive Algorithm for Spatial Greyscale" by R. W. Floyd and L. Steinberg, Proceeding of the SID 17/2, pp. 75-77 (1976), is a popular technique for halftoning used today and is considered to be one of the best, and the best among the techniques with similar operating time. This technique and others are reviewed in the book Digital Halftoning, MIT Press, Cambridge, Mass. (1987), by R. Ulichney which is a general reference for digital halftoning.
The operation of error diffusion basically spreads the error occurring at a given pixel across neighboring pixels. The spreading of the error is described by an ordered set of numbers called filter coefficients forming together an error filter. At each point, the input image data is combined with the diffused error and a printing decision is made according to some threshold. After Floyd and Steinberg, supra, other filters were proposed, in particular by J. F. Jarvis, C. N. Judice and W. H. Ninke in "A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays", Computer Graphics and Image Processing, Vol. 5, pp. 13-40 (1976), and by P. Stucki "MECCA--A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction", IBM Res. Rep., RZ1060 (1981). Stucki also considers the problem of compensating for actual black dot sizes and shapes, which is important since the basic method assumes square black and white dots of the same size while, in practice, printed dots are not square and overlap neighboring pixels. Filter coefficients are chosen as positive in practical implementations presented so far, but negative values have been considered for special effects and for theoretical studies, for instance in "Stability of Active Binarization Processes", Opt. Commun., 60, pp. 353-358 (1986), by M. Broja, R. Eschbach, and O. Bryngdahl.
Error diffusion has been further enriched, for instance, by varying the threshold in order to cluster dots or to reduce artifacts, for instance, in "Halftoning Techniques Using Error Correction", Proceedings of the SID, Vol. 27/4, pp. 305-308 (1986), by G. S. Fawcett and G. F. Schrack, in U.S. Pat. No. 5,055,942 to R. L. Levien, in U.S. Pat. No. 5,150,429 to R. L. Miller and C. M. Smith, or in U.S. Pat. No. 5,325,211 to R. Eschbach. Error diffusion has also been enriched by varying the filter according to grey regions and compensating for the problems hereby introduced, in order to reduce artifacts, for instance in "Computer-generated Holograms with Pulse-density Modulation", J. Opt. Soc. Al (1984) 5-10, by R. Hauck and O. Bryngdhal, or in "Reduction of Artifacts in Error Diffusion by Means of Input-dependent Weights", J. El. Imag. 2(4) (1993) 352-358, by R. Eschbach. These further enrichments, however, fail to correct all problems associated with error diffusion methods.
In all variations of error diffusion, the pixels are processed one at a time following some sequential raster ordering. Because of this sequential processing, the resulting operation is asymmetric, in the sense that it treats pixels differently depending on where they are in the sequential ordering. The results of this are anisotropic algorithmic artifacts, resembling "worms", occurring in the halftoned picture. This is one of the major drawbacks of error diffusion. Several partial solutions have been proposed to this major problem, in particular in the references cited above.
Error diffusion does not allow for good representation for most uniform greys and, in particular, fails to generate most of the pleasant periodic patterns generated by passive methods which use a dithering mask. Furthermore, periodic patterns are usually rather avoided, as discussed for instance in "Limit Cycle Behavior of Error Diffusion", Proceedings ICIP 94 Vol. 2, pp. 1041-1045 (1994), by Z. Fan and R. Eschbach, because they are hard to mix with aperiodic textures which contain worms.
The way uniform greys are rendered is mostly unpredictable when using error diffusion methods as described in the prior art. This induces bad representation of most uniform greys which in turn reduces contour definition and forces a trade-off between contour definition and trying to suppress undesirable artifacts such as lines at the boundary of an otherwise almost uniformly colored region, as reported for instance in "Error-diffusion Algorithm with Edge Enhancement", J. Opt. Soc. Am., A8, pp. 1844-1850 (1991), by R. Eschbach and K. T. Knox, or in "Threshold Modulation in Error Diffusion", J. El. Imag., 2(3), pp. 185-192 (1993), by K. T. Knox and R. Eschbach. The unpredictability of the rendering of uniform greys also makes it harder to calibrate according to printer performances as discussed for instance in "Measurement of Printer Parameters for Model-based Halftoning", J. El. Imag., 2(3), pp. 193-204 (1993), by T. N. Pappas, C. K. Dong, and D. L. Neuhoff or in "Measurement based Evaluation of a Printer Dot Model for Halftone Algorithm Tone Correction", J. El. Imag., 2(3), pp. 205-212 (1993), by C. J. Rosenberg, making it preferable to use model-based error diffusion as described for instance in "Printer Models and Error Diffusion", IEEE Transactions on Image Processing, 4(1), pp. 66-80 (1995), by T. N. Pappas and D. L. Neuhoff.